#pragma once
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<set>
using namespace std;
namespace open_address
{
	template<class T>
	struct DefaultHashFunc
	{
		size_t operator()(const T& _data)
		{
			return (size_t)_data;
		}
	};
	template<>
	struct DefaultHashFunc<string>
	{
		size_t operator()(const string& str)
		{
			size_t hash = 0;
			for (auto ch : str)
			{
				hash *= 131;
				hash += ch;
			}

			return hash;
		}
	};
	enum STATE
	{
		EXIST,
		EMPTY,
		DELETE
	};
	template<class K,class V>
	struct Hash_Data
	{
		pair< K, V> kv;
		STATE _state = EMPTY;
	};
	template<class K,class V,class Hashfunc= DefaultHashFunc<K>>
	class Hash_Table
	{
	public:
		Hash_Table()
		{
			_table.resize(10);
		}
		DefaultHashFunc<K> hs;
		bool Insert(const pair<K, V>& _kv)
		{
			if (Find(_kv.first))
			{
				return false;
			}
			if (_n * 10 / _table.size() >= 7)
			{
				Hash_Table<K,V> newtable;
				newtable._table.resize(_table.size() * 2);
				for (int i = 0; i < _table.size(); i++)
				{
					newtable.Insert(_table[i].kv);
				}
				std::swap(newtable._table,_table);
			}
			size_t _data = hs(_kv.first) % _table.size();
			while (_table[_data]._state == EXIST)
			{
				_data++;
				_data %= _table.size();
			}
			_table[_data].kv = _kv;
			_n++;
			_table[_data]._state = EXIST;
			return true;
		}
	Hash_Data<const K, V>* Find(const K& data)
		{
			size_t _data = hs(data) % _table.size();
			while (_table[_data]._state != EMPTY)
			{
				if (_table[_data]._state == EXIST&&
					_table[_data].kv.first == data)
				{
					return (Hash_Data<const K, V>*) & _table[_data];
				}
				_data %= _table.size();
				_data++;
			}
			return nullptr;
		}
	bool Erase(const K& key)
	{
		Hash_Data<const K, V>* ret = Find(key);
		if (ret)
		{
			_n--;
			ret->_state = DELETE;
			return true;
		}
		return false;
	}
	private:
		size_t _n=0;
		vector<Hash_Data<K, V>> _table;
	};
}
namespace hash_bucket
{
	template<class T>
	struct DefaultHashFunc
	{
		size_t operator()(const T& _data)
		{
			return (size_t)_data;
		}
	};
	template<>
	struct DefaultHashFunc<string>
	{
		size_t operator()(const string& str)
		{
			size_t hash = 0;
			for (auto ch : str)
			{
				hash *= 131;
				hash += ch;
			}

			return hash;
		}
	};
	template<class K, class V>
	struct Hash_Data
	{
		pair< K, V> kv;
		Hash_Data* next=nullptr;
	};
	template<class K, class V, class Hashfunc = DefaultHashFunc<K>>
	class Hash_Table
	{
	public:
		typedef Hash_Data<K, V> Node;
		Hashfunc hs;
		Hash_Table()
		{
			_table.resize(10, nullptr);
		}
		~Hash_Table()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
					cur = next;
				}
			_table[i]=nullptr;
			}
		}
		Hash_Data<const K, V>* Find(const K& data)
		{
			size_t _data = hs(data) % _table.size();
			Node* cur = _table[_data];
			while (cur)
			{
				if (cur->kv.first == data)
				{
					return 	(Hash_Data<const K, V>*) cur;
				}
				cur = cur->next;
			}
			return nullptr;
		}
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}
			if (_n / _table.size() == 1)
			{
				Hash_Table newtable;
				newtable._table.resize(2 * _table.size());
				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						newtable.Insert(cur->kv);
						cur = cur->next;
					}
					_table[i] = nullptr;
				}
				swap(newtable._table, _table);
			}
			size_t _data = hs(kv.first) % _table.size();
			Node* node = new Node;
			node->kv = kv;
			node->next = _table[_data];
			 _table[_data]=node;
			_n++;
		}
		bool Erase(const K& key)
		{
			size_t _data = hs(key) % _table.size();
			Node* cur = _table[_data];
			while (cur)
			{
				if (cur->kv.first == key)
				{
					break;
				}
				cur = cur->next;
			}
			if (cur == nullptr)
				return false;
			Node* ptr = _table[_data];
			if (ptr == cur)
			{
				_table[_data] = ptr->next;
				delete ptr;
				return true;
			}
			while (1)
			{
				if (ptr->next== cur)
				{
					break;
				}
				ptr = ptr->next;
			}
			ptr->next = ptr->next->next;
			cur->next = nullptr;
			delete cur;
			return true;
		}
		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->kv.first <<":"<< cur->kv.second<< "->";
					cur = cur->next;
				}
				printf("NULL\n");
			}
			cout << endl;
		}
	private:
		size_t _n = 0;
		vector<Node*> _table;
	};
};